package com.leetcode.LeetCode精选TOP面试题;

/**
 * @author 覃国强
 * @date 2022-05-09 18:31
 */
public class 题库_0004_寻找两个正序数组的中位数 {

  public static void main(String[] args) {
    int[] nums1 = {1, 2};
    int[] nums2 = {3, 4};

    double medianSortedArrays = new Solution().findMedianSortedArrays(nums1, nums2);
    System.out.println(medianSortedArrays);
  }

  static
  class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
      boolean nums1IsNull = nums1 == null || nums1.length == 0;
      boolean nums2IsNull = nums2 == null || nums2.length == 0;
      if (nums1IsNull && nums2IsNull) {
        return 0;
      }
      int length = (!nums1IsNull ? nums1.length : 0) + (!nums2IsNull ? nums2.length : 0);
      if (nums1IsNull || nums2IsNull) {
        if (length % 2 == 1) {
          return !nums1IsNull ? nums1[length / 2] : nums2[length / 2];
        } else {
          return !nums1IsNull ? (1.0 * nums1[length / 2 - 1] + nums1[length / 2]) / 2 : (1.0 * nums2[length / 2 - 1] + nums2[length / 2]) / 2;
        }
      }

      if (length % 2 == 1) {
        return getKthNum(nums1, nums2, length / 2 + 1);
      } else {
        return (getKthNum(nums1, nums2, length / 2) + getKthNum(nums1, nums2, length / 2 + 1)) / 2.0;
      }
    }

    private int getKthNum(int[] nums1, int[] nums2, int k) {

      int s1 = 0;
      int s2 = 0;

      while (k > 1) {
        int offset = k / 2 - 1;
        int p1 = Math.min(s1 + offset, nums1.length - 1);
        int p2 = Math.min(s2 + offset, nums2.length - 1);
        if (nums1[p1] <= nums2[p2]) {
          k -= (p1 - s1 + 1);
          s1 = p1 + 1;
        } else {
          k -= (p2 - s2 + 1);
          s2 = p2 + 1;
        }

        if (s1 >= nums1.length) {
          return nums2[s2 + k - 1];
        }
        if (s2 >= nums2.length) {
          return nums1[s1 + k - 1];
        }
      }

      return Math.min(nums1[s1], nums2[s2]);
    }
  }

}
